#include "sort.h"

// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 稳定性：稳定
void bubble_sort_1(int *arr, int n) {
    For(i, 0, n - 1) For(j, i + 1, n) if (arr[i] > arr[j]) SWAP(arr[i], arr[j]);
}

void bubble_sort_2(int *arr, int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1]) SWAP(arr[j], arr[j + 1]);
}

void bubble_sort_3(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int flag = 1;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                SWAP(arr[j], arr[j + 1]);
                flag = 0;
            }
        }
        if (flag) break;
    }
}

// 选择排序
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 稳定性：不稳定
void select_sort_1(int *arr, int n) {
    For(i, 0, n) {
        int min_idx = i;
        For(j, i + 1, n) if (arr[j] < arr[min_idx]) min_idx = j;
        SWAP(arr[i], arr[min_idx]);
    }
}

void select_sort_2(int *arr, int n) {
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        int min_idx = left, max_idx = right;
        For(i, left + 1, right + 1) {
            if (arr[i] < arr[min_idx])
                min_idx = i;
            else if (arr[i] > arr[max_idx])
                max_idx = i;
        }
        SWAP(arr[left], arr[min_idx]);
        if (max_idx == left) max_idx = min_idx;
        SWAP(arr[right], arr[max_idx]);
    }
}

// 插入排序
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 稳定性：稳定
void insert_sort(int *arr, int n) {
    For(i, 0, n) {
        int min = arr[i];
        int j = i - 1;
        for (; j >= 0; --j) {
            if (arr[j] > min)
                arr[j + 1] = arr[j];
            else
                break;
        }
        arr[j + 1] = min;
    }
}

// 希尔排序
// 时间复杂度：O(nlogn)到O(n^2)，取决于增量序列
// 空间复杂度：O(1)
// 稳定性：不稳定
void shell(int *arr, int n, int gap) {
    For(i, gap, n) {
        int min = arr[i];
        int j = i - gap;
        for (; j >= 0; j -= gap)
            if (arr[j] > min)
                arr[j + gap] = arr[j];
            else
                break;
        arr[j + gap] = min;
    }
}

void shell_sort(int *arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap /= 2;
        shell(arr, n, gap);
    }
}

// 堆排序
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
// 稳定性：不稳定
void sift_down(int *arr, int n, int root, int end) {
    int child = root * 2 + 1;
    while (child < end) {
        if (child + 1 < end && arr[child + 1] > arr[child]) {
            ++child;
        }
        if (arr[child] > arr[root]) {
            SWAP(arr[child], arr[root]);
            root = child;
            child = root * 2 + 1;
        } else {
            break;
        }
    }
}
void heapify(int *arr, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; --i) sift_down(arr, n, i, n);
}

void heap_sort(int *arr, int n) {
    heapify(arr, n);
    int end = n - 1;
    while (end > 0) {
        SWAP(arr[0], arr[end]);
        sift_down(arr, n, 0, end);
        --end;
    }
}

// 归并排序
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
// 稳定性：稳定
void merge(int *arr, int left, int mid, int right) {
    int len = right - left + 1;
    int *temp = MALLOC(int, len);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    For(i, 0, len) arr[left + i] = temp[i];
    free(temp);
}
void merge_sort_inner(int *arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    merge_sort_inner(arr, left, mid);
    merge_sort_inner(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void merge_sort(int *arr, int n) { merge_sort_inner(arr, 0, n - 1); }

// 归并排序-非递归
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
// 稳定性：稳定
void merge_sort_nor(int *arr, int n) {
    for (int gap = 1; gap < n; gap *= 2) {
        for (int left = 0; left < n; left += gap * 2) {
            int mid = MIN(left + gap - 1, n - 1);
            int right = MIN(mid + gap, n - 1);
            merge(arr, left, mid, right);
        }
    }
}

// 快速排序
// 时间复杂度：O(nlogn)（平均情况），O(n^2)（最坏情况）
// 空间复杂度：O(logn)（递归栈空间）
// 稳定性：不稳定
int partition_1(int *arr, int left, int right) {
    int base = arr[left];
    int temp = left;
    while (left < right) {
        while (left < right && arr[right] >= base) --right;
        while (left < right && arr[left] <= base) ++left;
        SWAP(arr[left], arr[right]);
    }
    SWAP(arr[temp], arr[left]);
    return left;
}
int partition_2(int *arr, int left, int right) {
    int base = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= base) --right;
        arr[left] = arr[right];
        while (left < right && arr[left] <= base) ++left;
        arr[right] = arr[left];
    }
    arr[left] = base;
    return left;
}
// 该方法不适配非递归快速排序
int partition_3(int *arr, int left, int right) {
    int prev = left, cur = left + 1;
    while (cur <= right) {
        if (arr[cur] < arr[left] && ++prev != cur) SWAP(arr[prev], arr[cur]);
        ++cur;
    }
    SWAP(arr[prev], arr[left]);
    return prev;
}
int partition_4(int *arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    For(j, left, right) {
        if (arr[j] < pivot) {
            i++;
            SWAP(arr[i], arr[j]);
        }
    }
    SWAP(arr[i + 1], arr[right]);
    return i + 1;
}

void quick_sort_inner_1(int *arr, int left, int right) {
    if (left >= right) return;
    int base = partition_1(arr, left, right);
    quick_sort_inner_1(arr, left, base - 1);
    quick_sort_inner_1(arr, base + 1, right);
}

void insert_sort_in_quick_sort(int *arr, int left, int right) {
    For(i, left + 1, right + 1) {
        int cur = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > cur) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = cur;
    }
}

int get_mid(int *arr, int left, int right) {
    int mid = (left + right) / 2;
    if (arr[left] > arr[mid]) SWAP(arr[left], arr[mid]);
    if (arr[left] > arr[right]) SWAP(arr[left], arr[right]);
    if (arr[mid] > arr[right]) SWAP(arr[mid], arr[right]);
    return mid;
}

void quick_sort_inner_2(int *arr, int left, int right) {
    if (left >= right) return;
    if (right - left < 8) {
        insert_sort_in_quick_sort(arr, left, right);
        return;
    }
    int mid = get_mid(arr, left, right);
    SWAP(arr[mid], arr[left]);
    int base = partition_2(arr, left, right);
    quick_sort_inner_2(arr, left, base - 1);
    quick_sort_inner_2(arr, base + 1, right);
}

void quick_sort_1(int *arr, int n) { quick_sort_inner_1(arr, 0, n - 1); }
void quick_sort_2(int *arr, int n) { quick_sort_inner_2(arr, 0, n - 1); }

#include "SequentialStack.h"
typedef struct SequentialStack Stack;

void quick_sort_nor_inner(int *arr, int left, int right) {
    Stack *stack = init_stack();
    int base = partition_4(arr, left, right);
    if (base > left + 1) {
        push(stack, left);
        push(stack, base - 1);
    }
    if (base < right - 1) {
        push(stack, base + 1);
        push(stack, right);
    }
    while (!is_empty(stack)) {
        right = pop(stack);
        left = pop(stack);
        base = partition_4(arr, left, right);
        if (base > left + 1) {
            push(stack, left);
            push(stack, base - 1);
        }
        if (base < right - 1) {
            push(stack, base + 1);
            push(stack, right);
        }
    }
}
// 快速排序-非递归
// 时间复杂度：O(nlogn)（平均情况），O(n^2)（最坏情况）
// 空间复杂度：O(n)（栈空间）
// 稳定性：不稳定
void quick_sort_nor(int *arr, int n) { quick_sort_nor_inner(arr, 0, n - 1); }

// 计数排序
// 时间复杂度：O(n+k)，其中k是数组的范围
// 空间复杂度：O(k)
// 稳定性：不稳定
void count_sort(int *arr, int n) {
    int max = arr[0], min = arr[0];
    For(i, 1, n) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    int len = max - min + 1;
    // 因为需要计数，所以要用calloc自动初始化为0
    int *count = CALLOC(int, len);
    For(i, 0, n) count[arr[i] - min]++;
    int idx = 0;
    For(i, 0, len) while (count[i]--) arr[idx++] = i + min;
    free(count);
}

// 计数排序-稳定版
// 时间复杂度：O(n+k)，其中k是数组的范围
// 空间复杂度：O(n+k)
// 稳定性：稳定
void count_sort_stable(int *arr, int n) {
    int max = *arr, min = *arr;
    For(i, 1, n) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    int len = max - min + 1;
    int *count = CALLOC(int, len);
    For(i, 0, n)++ count[arr[i] - min];
    For(i, 1, len) count[i] += count[i - 1];
    int *temp = MALLOC(int, n);
    for (int i = n - 1; i >= 0; --i) temp[--count[arr[i] - min]] = arr[i];
    For(i, 0, n) arr[i] = temp[i];
    free(temp);
}
